/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
/*
  // 数组双指针 O(n),O(n)
    bool isPalindrome(ListNode* head) {
        vector<int> v;  // 将链表val放入数组
        ListNode* cur = head;
        while(cur != nullptr){
            v.push_back(cur->val);
            cur = cur->next;
        }
        for(int i = 0,j = (int)v.size()-1; i < j; ++i,--j){
            if(v[i] != v[j])
                return false;
        }
        return true;
    }
*/

    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head, *next;
        while(cur != nullptr){
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        head = pre;
        return head;
    }

    // 双指针反转
    bool isPalindrome(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return true;
        // 1.找到前半部分链表的尾节点为mid。  
        ListNode* mid = head, *tail = head;
        while(tail->next != nullptr && tail->next->next != nullptr){
            mid = mid->next;
            tail = tail->next->next;
        }
        // 2.反转后半部分链表。 
        ListNode* backhalf = reverseList(mid->next); 
       
        // 3.判断是否回文。 
        bool ret = true;
        ListNode* p1 = head, *p2 = backhalf;
          /**   反转后（如果长度为奇数）前半部分较长，所以以短地后半部分长度和返回结果作为循环判断条件 **/
        while(ret && p2 != nullptr){
            if(p1->val != p2->val)   
                ret = false;
            p1 = p1->next;
            p2 = p2->next;
        }
        // 4.恢复链表。 
        mid->next = reverseList(backhalf);
        // 5.返回结果。
        return ret;
    }
};